Recursive insertion returns the node that should occupy a certain position.
- Base Case: If the current node is None, we have found the empty spot. We create a new Node and return it. This returned node will be assigned to the parent's .left or .right pointer in the previous call.
- Recursive Step: We recurse down the left or right subtree. The crucial part is node.left = insert(...). We are re-assigning the child pointer to be whatever the recursive call returns—either the existing child or the newly created node.
- If the key already exists, no recursive calls are made, and the original node is returned, leaving the tree structure unchanged.
def insert(node, key):
"""Inserts a key into the BST recursively."""
# Base Case: Found the empty spot to insert.
if node is None:
return Node(__________)
# Recursive Step: Recurse down the tree.
if key < node.key:
# Result of call becomes the new left child.
node.left = insert(__________, key)
elif key > node.key:
# Result of call becomes the new right child.
node.right = insert(__________, key)
# Return the (possibly modified) node.
return node
Copied!